package BinaryTree.快排归并;

import 其他.DataStructure.ListNode;
import MyUtils.ListUtils;
import org.junit.Test;

/**
 * 大技：
 *    分治 , 参lr -> 汉译 递归
 *
 * 合 = 切
 * LHead  = mergeSort(h, mid);
 * 后左侧↑    先右侧 ↓
 *
 */
public class 归并_排序链表148 {
    public ListNode sortList(ListNode head) {
        // 先基础框架
        ListNode tail = head;
        while(tail.next!=null){
            tail = tail.next;
        }
        return merge_sort_link(head, tail);
    }
    private ListNode merge_sort_link(ListNode head, ListNode tail) {
        if(head==tail){
            return head; // return head
        }

        //找中点
        ListNode mid = findMidNode(head, tail);

        // 类似 max
        ListNode afterMergeNewOneHead_Left = merge_sort_link(head, mid);
        ListNode tmpMidNext = mid.next;
        mid.next = null; // a=b 只动左a
        ListNode afterMergeNewOneHead_Right =merge_sort_link(tmpMidNext, tail);

        // 后序
        return merge2OrderLink(afterMergeNewOneHead_Left,afterMergeNewOneHead_Right); // 返回 合一 的 左head
    }

    // 合并有序 链表
    /*
        画图吧 注释不好弄 123
    */
    private ListNode merge2OrderLink(ListNode h1, ListNode h2) {
        ListNode dm = new ListNode(-1);
        ListNode dmt = dm;

        while(h1!=null && h2!=null){ // 不是h1.next
            if(h1.val<=h2.val){
                // 圈123
                dm.next = h1;
                dm = dm.next;
                h1 = h1.next;
            }else {
                dm.next = h2;
                dm = dm.next;
                h2 = h2.next;
            }
        }
        if(h1 == null){
            dm.next = h2;
        }
        if(h2 == null){
            dm.next = h1;
        }
        return dmt.next;
    }

    // 链表 找中点
    private ListNode findMidNode(ListNode head, ListNode tail) {
        ListNode fast = head.next, slow = head;
        while (fast != tail.next && fast.next != tail.next) { // 不是n/t 是 t.n
            slow = slow.next;
            fast = fast.next.next;
        }
        return slow;
    }

    @Test
    public void test() {
//        ListNode l1 = new ListNode(1);
//        ListNode l2 = new ListNode(1);
//        ListNode l3 = new ListNode(2);
//        l1.next=l2; l2.next=l3;
//        ListNode ll1 = new ListNode(1);
//        ListNode ll2 = new ListNode(2);
//        ListNode ll3 = new ListNode(3);
//        ll1.next = ll2; ll2.next=ll3;
//
//        ListNode resHead = merge2OrderLink(l1, ll1);
//        System.out.println(1);
        ListNode l1 = new ListNode(-1);
        ListNode l2 = new ListNode(5);
        ListNode l3 = new ListNode(3);
        ListNode l4 = new ListNode(4);
        ListNode l5 = new ListNode(0);
        l1.next=l2;l2.next=l3;l3.next=l4;l4.next=l5;

        ListNode resHead = sortList(l1);
        ListUtils.ptListByHead(resHead);
    }















}
